In OFDM communications systems the frequencies and modulation of a frequency-division multiplexing (FDM) communications signal are arranged orthogonal with each other to eliminate interference between signals on each frequency. In this communications system, low-rate modulations with relatively long symbols compared to the channel time characteristics are less sensitive to multipath propagation issues. OFDM transmits a number of low symbol-rate data streams on separate narrow frequency subbands using multiple frequencies simultaneously, instead of transmitting a single, high symbol-rate stream on one wide frequency band on a single frequency. These multiple subbands have the advantage that the channel propagation effects are generally more constant over a given subband than over the entire channel as a whole. A classical In-phase/Quadrature (I/Q) modulation can be transmitted over individual subbands. Also, OFDM is typically used in conjunction with a Forward Error Correction scheme, which in this instance is sometimes termed Coded Orthogonal FDM or COFDM.
As known to those skilled in the art, an OFDM signal can be considered the sum of a number of orthogonal subcarrier signals, with baseband data on each individual subcarrier independently modulated, for example, by Quadrature Amplitude Modulation (QAM) or Phase-Shift Keying (PSK). This baseband signal can also modulate a main RF carrier.
OFDM signals are generally created by performing the inverse Fourier transform on the data, with the Inverse Fast Fourier Transform (IFFT) becoming the preferred method since it is numerically efficient. Additionally, OFDM demodulation requires use of the Fourier Transform. This is typically implemented with a Fast Fourier Transform (FFT) requiring complex multiplications in an OFDM receiver that decodes a packet of k-symbols requiring complex multiplications.
An algorithm's efficiency, such as the FFT or IFFT, is typically measured by the number of required multiplications and additions. The hardware implementation complexity is usually determined by the number of multiplications-per-second, since multipliers typically take up more real estate and clock-cycles on processors and VLSI designs. Direct evaluation of the N-point discrete Fourier Transform (DFT) requires N2 complex multiplications and N*(N−1) complex additions, or 4*N2 real multiplications and N*(4*N−2) real additions. The DFT of a finite-length sequence of length N is:
                    X        ⁡                  [          k          ]                    =                        ∑                      n            =            0                                N            -            1                          ⁢                              x            ⁡                          [              n              ]                                ·                      W            N            kn                                ,          k      =              0        ,        1              ,    …    ⁢                  ,          N      -      1                          x        ⁡                  [          n          ]                    =                        1          N                ⁢                              ∑                          n              =              0                                      N              -              1                                ⁢                                    X              ⁡                              [                k                ]                                      ·                          W              N                              -                kn                                                          ,          n      =              0        ,        1              ,    …    ⁢                  ,          N      -      1      where W is the twiddle factor matrix with the elements defined by the complex exponential
WNn·k=ej·2·π·n·k/N for k=0, 1, . . . , N−1 and n=0, 1, . . . , N−1.
As known to those skilled in the art, the fast Fourier Transform (FFT) is a set of algorithms that substantially reduce the number of computations required to compute the DFT. The radix-R FFT algorithms operate by splitting the N-point DFT into v stages, where v is an integer and N=Rv. The well-known radix-2 algorithm (N=2v) is based on decomposing the sequence x[n] into successively smaller sub-sequences for processing by smaller DFT's and is referred to as a decimation-in-time algorithm. Accordingly, the radix-2 algorithm that decomposes the Fourier coefficients into smaller sub-sequences is called a decimation-in-frequency algorithm. These algorithms exploit both the periodicity and symmetry of the twiddle factor matrix. The radix-2 algorithm requires
      N    2    ·            log      2        ⁡          (      N      )      complex multiplications and N·log2(N) complex additions. In other words, the computation workload is reduced by
  N            log      2        ⁡          (      N      )      when compared to a direct evaluation of the DFT. If v=10, then N=1024 and the number of complex multiplications is 5120, which is more than 200 times more efficient than the DFT requiring 1048576 complex multiplications. A radix-4 algorithm [4] requires
      3    8    ·  N  ·      (                            log          2                ⁡                  (          N          )                    -      2        )  complex multiplications and N·log2(N) additions.
Since these calculations are performed on data blocks of length N, the number of multiplications per sample is log2(N) for the IFFT. A 1024-point IFFT will require 5120 multipliers, or 5 multiplications per input sample. The OFDM symbol can be seen as a sum of carriers fn(k) according to
      y    k    =                    ∑                  n          =                                                    -                N                            /              2                        +            1                                    N          /          2                    ⁢                        x          n                ⁢                  ⅇ                      ⅈ            ⁢                                                  ⁢            nk            ⁢                                                  ⁢            2            ⁢                          π              /              N                                            =                  ∑                  n          =                                                    -                N                            /              2                        +            1                                    N          /          2                    ⁢                        x          n                ⁢                              f            n                    ⁡                      (            k            )                              and rewritten into the more common form
      y    k    =            ∑              n        =        0                    N        -        1              ⁢                  x        n            ⁢              ⅇ                  ⅈ          ⁢                                          ⁢          nk          ⁢                                          ⁢          2          ⁢                      π            /            N                              
The number of multiplications using the FFT or IFFT greatly impact hardware complexity and increases gate count. Also, there is significant implementation loss due to fixed-point rounding error.
Additionally, the problems associated with the Peak to Average Power Ratio (PAPR) using OFDM is further motivation to generate techniques for simplifying the FFT and IFFT techniques used in generating OFDM communications signals. Commonly assigned U.S. Patent Publication No. 2005/0089116, the disclosure which is hereby incorporated by reference in its entirety, discloses a system that reduces peak-to-average power ratio. There is still a need, however, to simplify the IFFT and FFT.